In computational complexity theory, the Set Splitting problem is the following decision problem: given a family F of subsets of a finite set S, decide whether there exists a partition of S into two subsets S1, S2 such that all elements of F are split by this partition, i.e., none of the elements of F is completely in S1 or S2. It is an NP-complete problem. [1]
The optimization version of this problem is called Max Set Splitting and requires finding the partition which maximizes the number of split elements of F. It is an APX-complete[2] (and NP-hard) problem. The problem remains NP-hard even if all subsets in F contain the same fixed number of elements m greater than 1 [3]
The decision variant of Max Set Splitting, also called "Set Splitting" is stated as follows: given an integer k, whether there exists a partition of S which splits at least k subsets of F? If k taken to be a fixed parameter, then Set Splitting is fixed-parameter tractable, i.e., a polynomial algorithm exists for any fixed k.[3]
The Weighted Set Splitting is a variant in which the subsets in F have weights and the oblective is to maximize the total weight of the split subsets.